Not Applicable.
This invention relates to generally to a method and apparatus for transmitting of data on a communications network. More specifically, this invention relates to timely forwarding and delivery of data over the network and to their destination nodes. Consequently, the end-to-end performance parameters, such as, loss, delay and jitter, have either deterministic or probabilistic guarantees.
The proliferation of high-speed communications links, fast processors, and affordable, multimedia-ready personal computers brings about the need for wide area networks that can carry real time data, like telephony and video. However, the end-to-end transport requirements of real-time multimedia applications present a major challenge that cannot be solved satisfactorily by current networking technologies. Such applications as video teleconferencing, and audio and video group (many-to-many) multicasting generate data at a wide range of bit rates and require predictable, stable performance and strict limits on loss rates, end-to-end delay bounds, and delay variations (xe2x80x9cjitterxe2x80x9d). These characteristics and performance requirements are incompatible with the services that current circuit and packet switching networks can offer.
Circuit-switching networks, which are still the main carrier for real-time traffic, are designed for telephony service and cannot be easily enhanced to support multiple services or carry multimedia traffic. Its synchronous byte switching enables circuit-switching networks to transport data streams at constant rates with little delay and jitter. However, since circuit-switching networks allocate resources exclusively for individual connections, they suffer from low utilization under xe2x80x9cburstyxe2x80x9d traffic. Moreover, it is difficult to dynamically allocate circuits of widely different capacities, which makes it a challenge to support multimedia traffic. Finally, the synchronous byte switching of SONET, which embodies the Synchronous Digital Hierarchy (SDH), requires increasingly more precise clock synchronization as the lines speed increases [John C. Bellamy, Digital Network Synchronization, IEEE Communications Magazine, April 1995, pages 70-83].
Packet switching networks like IP (Internet Protocol)-based Internet and Intranets [see, for example, A. Tannebaum, Computer Networks (3rd Ed) Prentice Hall, 1996] and ATM (Asynchronous Transfer Mode) [see, for example, Handel et al., ATM Networks: Concepts, Protocols, and Applications, (2nd Ed.) Addison-Wesley, 1994] handle bursty data more efficiently than circuit switching, due to their statistical multiplexing of the packet streams. However, current packet switches and routers operate asynchronously and provide best effort service only, in which end-to-end delay and jitter are neither guaranteed nor bounded. Furthermore, statistical variations of traffic intensity often lead to congestion that results in excessive delays and loss of packets, there by significantly reducing the fidelity of real-time streams at their points of reception.
Efforts to define advanced services for both IP and ATM have been conducted in two levels: (1) definition of service, and (2) specification of methods for providing different services to different packet streams. The former defines interfaces, data formats, and performance objectives. The latter specifies procedures for processing packets by hosts and switches/routers. The types of services that defined for ATM include constant bit rate (CBR), variable bit rate (VBR) and available bit rate (ABR).
The methods for providing different services under packet switching fall under the general title of Quality of Service (QoS). Prior art in QoS can be divided into two parts: (1) traffic shaping with local timing without deadline scheduling, for example, [Demers et al., Analysis and Simulation Of A Fair Queuing Algorithm, ACM Computer Communication Review (SIGCOMM""89), pages 3-12, 1989; S. J. Golestani, Congestion-Free Communication In High-Speed Packet Networks, IEEE Transcripts on Communications, COM-39(12):1802-1812, December 1991; Parekh et al., A Generalized Processor Sharing Approach To Flow Controlxe2x80x94The Multiple Node Case, IEEE/ACM T. on Networking, 2(2):137-150, 1994], and (2) traffic shaping with deadline scheduling, for example [Ferrari et al., A Scheme For Real-Time Channel Establishment In Wide-Area Networks, IEEE Journal on Selected Areas in Communication, SAC-8(4):368-379, April 1990]. Both of these QoS approaches rely on manipulation of local queues by each router with little or no coordination with other routers. These approaches have inherent limitations when used to transport real-time streams. When traffic shaping without deadline scheduling is configured to operate at high utilization with no loss, the delay and jitter are inversely proportional to the connection bandwidth, which means that low rate connections may experience large delay and jitter inside the network. In traffic shaping with deadline scheduling the delay and jitter are controlled at the expense of possible congestion and loss.
The real-time transport protocol (RTP) [H. Schultzrinne et. al, RTP: A Transport Protocol for Real-Time Applications, IETF Request for Comment RFC 889, January 1996] is a method for encapsulating time-sensitive data packets and attaching to the data time related information like time stamps and packet sequence number. RTP is currently the accepted method for transporting real time streams over IP internetworks and packet audio/video telephony based on ITU-T H.323.
One approach to an optical network that uses synchronization was introduced in the synchronous optical hypergraph [Y. Ofek, The Topology, Algorithms And Analysis Of A Synchronous Optical Hypergraph Architecture, Ph.D. Dissertation, Electrical Engineering Department, University of Illinois at Urbana, Report No. UIUCDCS-R-87-1343, May 1987], which also relates to how to integrate packet telephony using synchronization [Y. Ofek, Integration Of Voice Communication On A Synchronous Optical Hypergraph, INFOCOM""88, 1988]. In the synchronous optical hypergraph, the forwarding is performed over hyper-edges, which are passive optical stars. In [Li et al., Pseudo-Isochronous Cell Switching In ATM Networks, IEEE INFOCOM""94, pages 428-437, 1994; Li et al., Time-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworking, IEEE INFOCOM""96, 1996] the synchronous optical hypergraph idea was applied to networks with an arbitrary topology and with point-to-point links. The two papers [Li et al., Pseudo-Isochronous Cell Switching In ATM Networks, IEEE INFOCOM""94, pages 428-437, 1994; Li et al., Time-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworking, IEEE INFOCOM""96, 1996] provide an abstract (high level) description of what is called xe2x80x9cRISC-like forwardingxe2x80x9d, in which a packet is forwarded, with little if any details, one hop every time frame in a manner similar to the execution of instructions in a Reduced Instruction Set Computer (RISC) machine.
Another related paper is [Baldi et al., End-to-End Delay Analysis of Videoconferencing Over Packet Switched Networks, IEEE INFOCOM 1998] which is a comparitive study of videoconferencing over Time-Driven Priority and various other packet-switched networks.
In accordance with the present invention, a method is disclosed providing virtual pipes that carry real-time traffic over packet switching networks while guaranteeing end-to-end performance. The method combines the advantages of both circuit and packet switching. It provides for allocation for the exclusive use of predefined connections and for those connections it guarantees loss free transport with low delay and jitter. When predefined connections do not use their allocated resources, other non-reserved data packets can use them without affecting the performance of the predefined connections.
Under the aforementioned prior art methods for providing packet switching services, switches and routers operate asynchronously. The present invention provides real-time services by synchronous methods that utilize a time reference that is common to the switches and end stations comprising a wide area network. The common time reference can be realized by using UTC (Coordinated Universal Time), which is globally available via, for example, GPS (Global Positioning Systemxe2x80x94see, for example: [Peter H. Dana, Global Positioning System (GPS) Time Dissemination for Real-Time Applications, Real-Time Systems, 12, pp. 9-40, 1997]. By international agreement, UTC is the same all over the world. UTC is the scientific name for what is commonly called GMT (Greenwich Mean Time), the time at the 0 (root) line of longitude at Greenwich, England. In 1967, an international agreement established the length of a second as the duration of 9,192,631,770 oscillations of the cesium atom. The adoption of the atomic second led to the coordination of clocks around the world and the establishment of UTC in 1972. The Time and Frequency Division of the National Institute of Standards and Technologies (NIST) (see http://www.boulder.nist.gov/timefreq) is responsible for coordinating UTC with the International Bureau of Weights and Measures (BIPM) in Paris.
UTC timing is readily available to individual PCs through GPS cards. For example, TrueTime, Inc.""s (Santa Rosa, Calif.) PCI-SG product provides precise time, with zero latency, to computers that have PCI extension slots. Another way by which UTC can be provided over a network is by using the Network Time Protocol (NTP) [D. Mills, Network Time Protocol (version 3) IETF RFC 1305]. However, the clock accuracy of NTP is not adequate for inter-switch coordination, on which this invention is based.
In accordance with the present invention, the synchronous virtual pipes (SVPs) are accessed by end-stations that are located across a shared media network. The shared media network can be of various types: IEEE P1394 and Ethernet for desktop computers and room area networks, cable modem head-end (e.g., DOCSIS, IEEE 802.14), wireless base-station (e.g., IEEE 802.11), and Storage Area Network (SAN) (e.g., FC-AL, SSA). The end-station can be of corresponding various types: for IEEE 1394: video cameras, VCR and video disk; for cable modem: set-top box with multiple Ethernet connections to video cameras, VCRs; for wireless: desktop computers and mobile units; and for SAN: disk drives, tape drives, RAM disks, electronic disks, and other storage devices.
More specifically:
IEEE P1394 [P1394 Standard for a High Performance Serial Bus, IEEE P1394 Draft 8.0v4, Nov. 21, 1995]xe2x80x94This standard describes a high speed, low cost serial bus suitable for use as a peripheral bus or a backup to parallel back-plane buses.
DOCSIS [Data-Over-Cable Service Interface Specifications Radio Frequency Interface Specification, SP-RFI-I04-980724]. The goal of this specification is to enable cable operators to deploy high-speed data communications systems on cable television systems. It provides definition, design, development and deployment of data-over-cable systems on an uniform, consistent, open, non proprietary, multi-vendor interoperable basis. The intended service will allow transparent bi-directional transfer of Internet Protocol (IP) traffic, between the cable system head-end and customer locations, over an all-coaxial or hybrid fiber/coax (HFC) cable network.
IEEE 802.14 [IEEE 802.14/a Draft 3 Revision 2 for Cable-TV access method and physical layer specification, Aug. 1, 1998], this standard is intended to provide complete support of Asynchronous Transfer Mode (ATM). This support comprises supporting the following: (1) The ATM layer service, as defined in ITU-T Recommendation I.150, (2) Transport of ATM cells across the HFC MAC, (3) The five ATM Service Categories defined in the ATM Forum Traffic Management specification, along with their associated Quality-of Service and traffic contract parameters, (4) Point-to-point and unidirectional point-to-multipoint ATM virtual connection links, (5) ATM Virtual Path (VP) and Virtual Channel (VC) links which are concatenated with other VP- and/or VC-links to form VP connections or VC connections, (6) Permanent Virtual Connections (PVCs) and Switched Virtual Connections (SVCs), including support for the ATM Forum Signaling 4.0 specification for establishing and releasing SVCs and the Integrated Layer Management Interface (formerly, Interim Layer Management Interface).
IEEE 802.11 [Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications, IEEE Std 802.11-1997]xe2x80x94the medium access control (MAC) and physical characteristics for wireless local area networks (LANs) are specified in this standard, part of a series of standards for local and metropolitan area networks. The medium access control unit in this standard is designed to support physical layer units as they may be adopted dependent on the availability of spectrum. This standard contains three physical layer units: two radio units, both operating in the 2400-2500 MHz band, and one base-band infrared unit. One radio unit employs the frequency-hopping spread spectrum technique, and the other employs the direct sequence spread spectrum technique.
There are several variants of Storage Area Network (SAN), for example: (1) ANSI standard X3T11, FC-ALxe2x80x94Fiber Channel Arbitrated Loop [see, for example, Robert W. Kembel, Arbitrated Loop, Connectivity Solutions, 1997], and (2) ANSI standard X3T10, SSAxe2x80x94Serial Storage Architecture [see, for example, Serial Storage Architecture A Technology Overview, Version 3.0, SSA Industry Association 1995]. SAN provides connectivity for a wide variety of storage devices, such as, disk drives, tape drives, RAM disks, electronic disks, and other storage devices. The underlying network for SSA is a ring network with concurrent access and spatial bandwidth reuse [Y. Ofek, Overview of the MetaRing Architecture, Computer Networks and ISDN Systems, Vol. 26, Nos. 6-8, March 1994, pp. 817-830], thus, a plurality of end-stations can send data packets to this type shared media network at the same time.
Fiber Channel (FC)xe2x80x94ANSI X3T11, using the arbitrated loop (AL) topology (abbreviated FC-AL) as a replacement for Small Computer Storage Interface (SCSI). Serial Storage Architecture (SSA) is a standard for peripheral interconnections, bringing with it higher levels of performance, availability, fault tolerance, and connectivity at low cost. FC-AL and SSA are high performance serial interfaces designed to connect disk drives, optical drives, tape drives, CD-ROMs, printers, scanners, and other peripherals to personal computers, workstations, servers, and storage subsystems. SSA and FC-AL facilitate migration from current SCSI equipment and will accommodate implementation of future configurations, including the use of fiber-optic connections.
These and other aspects and attributes of the present invention will be discussed with reference to the following drawings and accompanying specification.